﻿/*
题目: 完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

https://leetcode.cn/problems/perfect-squares/description/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    int numSquares(int n) {
        // dp[i] 表示 i 需要多少个完全平方数来组成
        vector<int> dp(n + 1, INT_MAX);
        dp[1] = dp[0] = 1;

        for (int i = 2; i <= n; i++) {
            if (ok(i) == true) {
                dp[i] = 1;
                continue;
            }

            // 否则，可以拆分
            for (int j = 1; j * j < i; j++) {
                dp[i] = min(dp[i], 1 + dp[i - j * j]);
            }
        }

        return dp[n];
    }

    bool ok(int num) {
        int s = ((int) ::sqrt(num));
        return (long long)s * s == num;
    }
};